Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.
Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1
Constraints:
1 <= wordsDict.length <= 3 * 1041 <= wordsDict[i].length <= 10wordsDict[i]consists of lowercase English letters.word1andword2are inwordsDict.word1 != word2
Average Rating: 4.75 (52 votes)
Solution
This is a straight-forward coding problem. The distance between any two positions i1 and i2 in an array is ∣i1−i2∣. To find the shortest distance between word1 and word2, we need to traverse the input array and find all occurrences i1 and i2 of the two words, and check if ∣i1−i2∣ is less than the minimum distance computed so far.
Approach #1 (Brute Force)
Algorithm
A naive solution to this problem is to go through the entire array looking for the first word. Every time we find an occurrence of the first word, we search the entire array for the closest occurrence of the second word.
Complexity Analysis
The time complexity is O(n2), since for every occurrence of word1, we traverse the entire array in search for the closest occurrence of word2.
Space complexity is O(1), since no additional space is used.
Approach #2 (One-pass)
Algorithm
We can greatly improve on the brute-force approach by keeping two indices i1 and i2 where we store the most recent locations of word1 and word2. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.
Complexity Analysis
-
Time complexity: O(N⋅M) where N is the number of words in the input list, and M is the total length of two input words.
-
Space complexity: O(1), since no additional space is allocated.
Last Edit: August 26, 2018 11:11 PM
You do not need currentDistance here.
Once we find the minDistance to be equal to 1, we can just return because it can never go down below that. This will help in saving some time as well if the first two words itself are word1 and word2.
September 10, 2018 10:40 PM
Don't need either currentDistance or to keep track of both indices:
min_dist = len(words)
curr_word, idx = None, 0
for i, w in enumerate(words):
if w not in (word1, word2): continue
if curr_word and w != curr_word:
min_dist = min(min_dist, i - idx)
curr_word, idx = w, i
return min_dist
Why the 2nd approach has Time complexity: O(N⋅M) and not O(N)? Why "the total length of two input words." influences the time complexity here?
Check words[i] is word1 or word2, else continue. This can save a little.
April 2, 2020 2:22 AM
My python submission
out = first = second = float('inf')
for i,word in enumerate(words):
if word == word1: first = i
elif word == word2: second = i
out = min(abs(first - second), out)
return out
This easy question in interview will turn into a super hard problem by maintaining list of indices for each word and performing a binary search and so on :-)
Just for fun, here is a more robust solution if we consider a few more edge cases (word 1 or word 2 are not in the list, etc).
public int shortestDistance(String[] words, String word1, String word2) {
if ((words == null) || (words.length == 0))
return -1;
int index_w1=-1, index_w2=-1;
int shortestDistance = Integer.MAX_VALUE;
for (int i=0; i<words.length; i++) {
if (words[i].equals(word1))
index_w1 = i;
if (words[i].equals(word2))
index_w2 = i;
// We found a new path between w1 and w2
if ((index_w1!=-1) && (index_w2!=-1)) {
shortestDistance = Math.min(shortestDistance, Math.abs(index_w1-index_w2));
}
}
return shortestDistance == Integer.MAX_VALUE? -1 : shortestDistance;
}
February 7, 2018 1:41 AM
def shortestDistance(self, words, word1, word2):
"""
:type words: List[str]
:type word1: str
:type word2: str
:rtype: int
"""
shortest = len(words)+1
index = None
found = None
for i, word in enumerate(words):
if word == word1 or word == word2:
if found is not None:
if word != found:
shortest = min(shortest, i - index)
found = word
index = i
return shortestTime Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/16/2021 09:29 | Accepted | 8 ms | 11.5 MB | cpp |
xxxxxxxxxxclass Solution {public: int shortestDistance(vector<string>& wordsDict, string word1, string word2) { int res = INT_MAX; int pos1 = -1, pos2 = -1; for(int i=0;i<wordsDict.size();i++) { if(wordsDict[i] == word1) pos1 = i; else if(wordsDict[i] == word2) pos2 = i; if(pos1 != -1 && pos2 != -1) { res = min(res, abs(pos1 - pos2)); } } return res; }};